package org.myy.learn.hot.贪心算法;

import lombok.extern.slf4j.Slf4j;

@Slf4j
public class 买卖股票的最佳时机 {


    /**
     * 高效法
     * 走到今天，去找历史的最低点，就是当天的最大利润
     * @param prices
     * @return
     */
    public static int maxProfitV2(int[] prices) {
        int minprices = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int i=0; i < prices.length; i++){
            if (prices[i] < minprices){
                minprices = prices[i];
            } else if(prices[i] - minprices > maxProfit){
                maxProfit = prices[i] - minprices;
            }
        }
        return maxProfit;
    }

    /**
     * 暴力法
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int i=0; i < prices.length; i++){
            int max = 0;
            for (int j=i+1; j < prices.length; j++){
                max = Math.max(max, prices[j] - prices[i]);
            }
            maxProfit = Math.max(maxProfit,max);
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = new int[]{7,1,5,3,6,4};
        int maxProfit = maxProfit(prices);
        int maxProfitV2 = maxProfitV2(prices);
        log.info("执行结束，最大利润={}, 最大利润={}", maxProfit, maxProfitV2);
    }
}
